The present invention relates to multimedia database systems and, more particularly, to query processing operations of composite multimedia objects. The invention provides an algorithm which prunes the search space by filtering multimedia objects in a ranked fuzzy cartesian query.
A composite object in a multimedia database is specified by a set of simple objects and the relationships among them. Each of the simple objects is characterized by one or many of its feature, spatial, temporal and semantic attributes. Relationships among simple objects can be spatial or temporal. Using an image database as an example, an image object may be defined by its color, shape, texture, or size. Relationships between two objects may be characterized using spatial relations such as xe2x80x9con top of,xe2x80x9d xe2x80x9cnear,xe2x80x9d or xe2x80x9cto the west of.xe2x80x9d As an example, one may define a composite object consisting of a xe2x80x9cred,xe2x80x9d xe2x80x9croundxe2x80x9d image object xe2x80x9cwithinxe2x80x9d a xe2x80x9clarge,xe2x80x9d xe2x80x9cwhitexe2x80x9d image area. This composite object is then used to search for images matching its description, such as one with a red beach ball on a white-sand beach. In the above example, xe2x80x9cred,xe2x80x9d xe2x80x9cround,xe2x80x9d xe2x80x9clargexe2x80x9d and xe2x80x9cwhitexe2x80x9d characterize features of simple objects. xe2x80x9cWithinxe2x80x9d defines the spatial relationship between the two simple objects.
In a multimedia database, object attributes and relationships are generally defined in fuzzy specifications and searches are targeted at retrieving top-K ranked objects in similarity, often known as a similarity search. For example, a search may involve searching for simple image objects which look xe2x80x9credxe2x80x9d and xe2x80x9cround.xe2x80x9d The property xe2x80x9credxe2x80x9d is measured by a fuzzy score on how close its color attribute is to xe2x80x9cred.xe2x80x9d The property xe2x80x9croundxe2x80x9d is measured by a fuzzy score on how close its shape attribute is to xe2x80x9cround.xe2x80x9d The overall score of the image object is calculated by taking a xe2x80x9cfuzzy ANDxe2x80x9d operation of the two individual property scores. Objects with their total scores ranked among the top-K are retrieved. Searches for composite objects are evaluated in a similar fashion, with the addition of fuzzy scores measuring object relationships.
While there have been extensive studies on querying simple objects, much less research is performed on processing composite objects. A composite object query involves evaluations of fuzzy cartesian products of the simple objects.
The present invention addresses a key issue in composite object queries, which is the reduction of the number of simple objects participating in evaluations of fuzzy cartesian products. Since fuzzy cartesians involve a lot of computation and disk retrieval, the smaller the number, the faster the query processing. The algorithm described in this invention guarantees the filtering of candidate objects does not cause any false dismissal. Top-K ranked composite objects retrieved from the filtered set of objects will be the same as those without filtering.
Techniques in retrieving image or video objects by their content features have progressed significantly in recent years. The cited publications below address indexing and query processing of similarity searches on simple objects, which may be characterized by multiple features. Related works include the IBM Query by Image Content (QBIC) system (M. Flickner et al., xe2x80x9cQuery by image and video content: The (QBIC) system,xe2x80x9d IEEE Computer, 28(9):23-32, September 1995), the Virage visual information retrieval system (J. R. Bach et al., xe2x80x9cVirage image search engine: an open framework for image management,xe2x80x9d Symposium on Electronic Imaging: Science and Technologyxe2x80x94Storage and Retrieval for Image and Video Databases (IV), volume 2670, pages 76-87, 1996), the MIT Photobook (A. Pentland et al., xe2x80x9cTools for content-based manipulation of image databases,xe2x80x9d Proceedings of the SPIE Storage and Retrieval Image and Video Databases II, February 1994), the Alexandria project at UCSB (B. S. Manjunath et al., xe2x80x9cTexture features for browsing and retrieval of image data,xe2x80x9d IEEE Trans. Pattern Analysis Machine Intell. Special Issue on Digital Libraries, (8), 1996, and M. Beatty et al., xe2x80x9cDimensionality reduction using multidimensional scaling for image search,xe2x80x9d Proc. IEEE International Conference on Image Processing, October 1997) and the IBM/NASA Satellite Image Retrieval System (C.-S. Li et al., xe2x80x9cProgressive content-based retrieval from distributed image/video databases,xe2x80x9d Proceeding of the International Symposium of Circuit and System, IEEE, 1997).
In recent years, the increasing importance for multimedia databases to provide search capabilities for not only simple but also composite objects has been recognized. Practical applications for composite object queries arise in both scientific and engineering disciplines. For example, they include:
Environmental epidemiology: Retrieve locations of houses which are vulnerable to epidemic diseases such as Hantavirus and Denge fever based on a combination of environmental factors (e.g., isolated houses that are near bushes or wetlands), and weather patterns (e.g., a wet summer followed by a dry summer).
Precision farming: (1) Retrieve locations of cauliflower crop developments that are exposed to clubroot, which is a soil-borne disease that infects cauliflower crop. Cauliflower and clubroot are recognized spectral signatures, and exposure results from their spatial and temporal proximity. (2) Retrieve those fields which have abnormal irrigation, (3) Retrieve those regions which have higher than normal soil temperature.
Precision forestry: (1) Calculate areas of forests that have been damaged by hurricane, forest fire, or storms. (2) Estimate the amount of the yield of a particular forest.
Petroleum exploration: Retrieve those regions which exemplify specific characteristics in the collection of seismic data, core images, and other sensory data.
Insurance: (1) Retrieve those regions which may require immediate attention due to natural disasters such as earthquake, forest fire, hurricane, and tornadoes. (2) Retrieve those regions having higher than normal claim rate (or amount) that are correlated to the geographyxe2x80x94close to coastal regions, close to mountains, in high crime rate regions, etc.
Medical image diagnosis: Retrieve all MRI images of brains that have tumors located within the hypothalamus. The tumors are characterized by shape and texture, and the hypothalamus is characterized by shape and spatial location within the brain.
Real estate marketing: Retrieve all houses that are near a lake (color and texture), have a wooded yard (texture) and are within 100 miles of skiing (mountains are also given by texture).
While composite object queries may be processed by evaluating each and every possible combination of fuzzy cartesian products, the computational complexity of this simple scan method is on the order of O(LN), where a composite object is defined by the relationships of N simple objects in a database of L candidates. In a recently filed patent application, the inventors described an algorithm to reduce the computational complexity to the order of O(K*N*L2), assuming top-K ranked composite objects are requested, see U.S. patent application identified as Ser. No. 09/237,734 filed on Jan. 26, 1999 in the names of Chung-Sheng Li et al. and entitled xe2x80x9cSystem and method for sequential processing of content-based retrieval of composite objects,xe2x80x9d the disclosure of which is incorporated by reference herein. A key idea behind the above-referenced Li et al. patent application is the observation that if the query only asked for top-K objects, at each node of the fuzzy cartesian, only K paths need to be kept, instead of L. As a result, the composite object query problem becomes much more tractable. However, there is still room for improvements since L is typically a large number exceeding 1,000.
A main contribution of the present invention is to further reduce the computational complexity to the order of O(K*N*M2), where M is a number less than or equal to L. The actual value of M is found through an algorithmic procedure detailed below in accordance with some illustrative embodiments of the present invention.
The present invention provides methods and apparatus for pruning the search space of simple multimedia objects involved in a ranked fuzzy cartesian query of composite objects. Particular aspects of the present invention are related to: (1) converting a query with a fuzzy specification of one or more simple objects and spatial or temporal relationships among them into a set of subgoals; (2) removing candidates in each subgoal which will not be part of the final top-K ranked composite; and (3) returning remaining candidates for fuzzy cartesian evaluation.
It is to be appreciated that a subgoal is the pairwise relationship between two simple objects specified in the query. The full fuzzy specification can be abstractly viewed as a graph of nodes and edges, where nodes represent simple objects and edges connecting the nodes represent subgoals. A simple object is an abstract notion or concept used in a query to describe the characteristics of a physical entity, e.g., car. Candidate objects or, more simply, candidates are the materialization of the object abstraction, e.g., Camry, Accord, and Explorer.
The present invention speeds up the query processing part on cartesian evaluation at the expense of pre-processing to prune the search space. Depending on the number of simple objects defined in the composite object query as well as distributions of their fuzzy scores, the speedup can be as much as several thousand fold. It should also be noted that in the worst case, there can be no speedup. However, since the computational overhead of pruning simple objects is small compared to the evaluation of a fuzzy cartesian, it is advisable to apply the algorithm in all circumstances.
The invention discloses two algorithms, the first of which prunes objects in a two-object fuzzy cartesian query and the second of which prunes objects in a query involving three or more objects. The two cases are treated separately because sufficient conditions to guarantee no false dismissal are less stringent in two-object queries. Less stringent conditions lead to a smaller pruned set of objects for cartesian evaluation, thereby increasing the processing speedup.
The two algorithms disclosed in the invention are applicable to any xe2x80x9cupward closedxe2x80x9d fuzzy AND operators. A fuzzy AND operator is a mapping of a vector of fuzzy scores to a single score. A fuzzy AND operator, f, is xe2x80x9cupward closedxe2x80x9d if and only if a vector X strictly greater than Y element wise implies f (X) greater than f (Y). Commonly used fuzzy AND operators such as minimum and weighted sum are xe2x80x9cupward closed.xe2x80x9d Note that the reverse is generally not true. That is, f(X) greater than f(Y) does not imply X strictly greater than Y element wise. The fuzzy AND operator takes the fuzzy scores of simple objects as well as their fuzzy relations as its argument. For example, a commonly used fuzzy AND operator is a linearly weighted sum. The fuzzy score of a composite multimedia object is then computed as a linearly weighted sum of fuzzy scores of simple objects and fuzzy relations. Weights assigned to each element may depend on applications and do not affect the algorithms described in this invention.
The first algorithm (two-object pruning algorithm) prunes the search space of composite objects comprising two simple objects. The algorithm first establishes a lower bound of the Kth largest composite object by making use of a sorted list of fuzzy relations between the two simple objects. This lower bound is then used to remove the set of candidates which have no opportunity to appear in the final top-K composites.
The second algorithm (multi-object pruning algorithm) prunes the search space of composite objects comprising three or more objects. The algorithm first divides the query into a set of subgoals, each of which is comprised of two simple objects and their fuzzy relation. Simple objects are pruned in each subgoal by using the first algorithm with additional constraints. When the subgoals are re-assembled, pruned objects may be selectively added back so that no false dismissal occurs.
The second algorithm is a realization of a set of sufficient conditions for object pruning. The set of sufficient conditions guarantee that for any path connecting pruned (removed) objects, there will be at least K paths in the remaining sets of objects having greater values. One can prove that any algorithm that performs a procedure satisfying the set of sufficient conditions will guarantee no false dismissal.
These and other objectives, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.